Many types of storage systems, including solid state storage systems, manage a logical-to-physical mapping table that tracks which one or more physical addresses (e.g., the actual location on the storage media where the data is actually kept) correspond to a given logical address (e.g., provided by a host during a write instruction and referenced by the host during the corresponding read instruction). Mapping tables are often stored on volatile memory, which is unable to retain information when there is no power. During a “graceful” power down where there is sufficient advance notice, the storage system copies the mapping table from volatile memory (e.g., on the storage controller) to non-volatile memory (e.g., the storage media itself). Then, when power is restored, the mapping table is retrieved. However, during an unexpected power down, the system does not have enough advance notice to copy the mapping table in its entirety to non-volatile memory. Although techniques exist for rebuilding a logical-to-physical mapping table, improved techniques which are able to rebuild the table in a faster manner would be desirable. It would also be desirable if such techniques were applicable to highly parallel, large capacity storage systems, for example, that have multiple storage dies.